package com.fosss.recursion;

/**
 * 二维数组表示棋盘
 */
public class IQueen8 {

    public static void main(String[] args) {
        IQueen8 queenTest = new IQueen8();
        queenTest.check(0);
    }

    private static final int QUEEN_NUM = 8;//皇后数量
    private int[][] board = new int[QUEEN_NUM][QUEEN_NUM];//棋盘
    static int count = 0;//解法数

    /**
     * @param row 第几个皇后
     */
    public void check(int row) {
        if (row == QUEEN_NUM) {
            print();//会回溯调用这个打印方法
            return;
        }
        for (int i = 0; i < board.length; i++) {//分别遍历每一行，也就是找到每一行的皇后

            if (isQueen(row, i)) {
                board[row][i] = 1;//假定该点为皇后的位置
                check(row + 1);
                //！！！！！！！！！！！！！！！！！！！
                //走到这时，说明之前的几行摆放已经无法在下面几行中找到合适位置，所以进行了回溯
                // 将上一个皇后清掉，
                // 利用残余棋盘查找被清掉的皇后下一种摆放方式
                //如果不行，则继续清掉上上个皇后，以此类推
                board[row][i] = 0;
            }

        }
    }

    /**
     * 判断是不是正确的位置
     */
    public boolean isQueen(int row, int col) {
        //判断正上方有没有
        for (int i = row - 1; i >= 0; i--) {
            if (board[i][col] == 1) {
                return false;
            }
        }

        //判断左上方有没有,行列每次都同时变换，来确保是正左上角
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        //判断右上方有没有,行列每次都同时变换，来确保是正右上角
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 1) {
                return false;
            }
        }
        return true;
    }

    /**
     * 打印棋盘
     */
    public void print() {
        count++;
        System.out.println("这是第" + count + "种解法");
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}






























